The present application is directed to searching and more particularly to computer based state-space searching. A particular challenge in computer programming for a state-space search is to make efficient use of available computer memory. Best-first search algorithms such as A* are often constrained by the amount of memory used to represent state-sets in the search frontier (the Open list), previously expanded states (the Closed list), and memory based heuristics including pattern databases (PDBs), which are a lookup tables that store the distance to the abstract goal of every abstract state (or “pattern”).
Although linear-space search algorithms such as IDA* (Depth-First Iterative Deepening) solve the memory problem for A*, they need extra node expansions to find an optimal solution, because linear-space search typically does not check for duplicates when successors are generated and this can lead to redundant work. Essentially, these algorithms trade time for space and their efficiency can vary dramatically, depending on the number of duplicates encountered in the search space. For domains with few duplicates such as the sliding puzzles, IDA* easily outperforms A*. But for other domains such as multiple sequence alignment, linear-space search simply takes too long. For STRIPS (Stanford Research Institute Problem Solver) planning, IDA* can expand many more nodes than A*, even if it uses a transposition table. As a result, state-of-the-art heuristic search planners such as Fast Downward (FD) use A* instead of IDA* as their underlying search algorithm.
A classic approach to improving the storage efficiency of A* is to use Binary Decision Diagrams (BDDs) to represent a set (or sets) of states compactly. By merging isomorphic sub-graphs, BDDs can be much more succinct than an equivalent explicit-state representation. For example, BDD-based planners such as MIPS (Model Checking Integrated Planning System) perform extremely well on domains like Gripper where BDDs are exponentially more compact than explicit state storage. However, such showcase domains for BDDs are only a small fraction of the benchmark problems found in planning, and most heuristic search planners still use explicit state representation, even though they can all benefit from having a succinct storage for state sets.